#include<iostream>
#include<string>
#include<vector>
using namespace std;


//  Definition for singly-linked list.
 struct ListNode {
  int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* Lstart = NULL;
        ListNode* Lend = NULL;
        ListNode* Rstart = NULL;
        ListNode* Rend = NULL;
        int i = 0;
        while (head != NULL) {
            if (i == 0) {
                if (Lstart == NULL && Lend == NULL) {
                    Lstart = head;
                    Lend = head;
                    head = head->next;
                    Lend->next = NULL;
                    i = 1;
                }
                else {
                    Lend->next = head;
                    Lend = head;
                    head = head->next;
                    Lend->next = NULL;
                    i = 1;
                }
            }
            else {
                if (Rstart == NULL && Rend == NULL) {
                    Rstart = head;
                    Rend = head;
                    head = head->next;
                    Rend->next = NULL;
                    i = 0;
                }
                else {
                    Rend->next = head;
                    Rend = head;
                    head = head->next;
                    Rend->next = NULL;
                    i = 0;
                }
            }
        }
        if (Lend!= NULL) {
            Lend->next = Rstart;
        }
        return Lstart;

    }
};


//int main() {
//    ListNode p1(2);
//    ListNode p2(1);
//    ListNode p3(3);
//    ListNode p4(5);
//    ListNode p5(6);
//    ListNode p6(4);
//    ListNode p7(7);
//
//    p1.next = &p2;
//    p2.next = &p3;
//    p3.next = &p4;
//    p4.next = &p5;
//    p5.next = &p6;
//    p6.next = &p7;
//
//    Solution S;
//    ListNode*T = S.oddEvenList(&p1);
//    return 0;
//
//}
